/*
 * @lc app=leetcode.cn id=354 lang=javascript
 *
 * [354] 俄罗斯套娃信封问题
 */

// @lc code=start
/**
 * @param {number[][]} envelopes
 * @return {number}
 */
var maxEnvelopes = function (envelopes) {
  const size = envelopes.length;
  if (size === 0) return 0;
  const binaySearch = (subs, target) => {
    let low = 0;
    let high = subs.length - 1;
    while (low < high) {
      let mid = low + ((high - low) >> 1);
      if (subs[mid] < target) {
        low = mid + 1;
      } else {
        high = mid;
      }
    }
    // 返回匹配的索引
    return low;
  };

  envelopes.sort((a, b) => {
    if (a[0] !== b[0]) {
      return a[0] - b[0];
    } else {
      return b[1] - a[1];
    }
  });

  const subs = [envelopes[0][1]];

  for (let i = 1; i < size; i++) {
    let height = envelopes[i][1];
    let subMaxHeight = subs[subs.length - 1];
    if (height > subMaxHeight) {
      subs.push(height);
    } else {
      const idx = binaySearch(subs, height);
      subs[idx] = height;
    }
  }
  return subs.length;
};
// @lc code=end
